Our previous patent disclosures describe a technology for determining position and timing of nodes in a network. These nodes are generally characterized as having independent, free running clocks, and one or more of the nodes is moving. The nodes communicate and share clock count information from which node position and clock parameters are derived. We refer to various embodiments of this technology as “space-time calibration,” “PhaseNet,” and “ZuluTime” (including the ZuluTime Web Service). For simplicity, we refer to this body of work as our space time calibration (STC) technology. This technology can be used to enhance the accuracy of positioning and timing within other systems, such as existing GPS or cell phone positioning systems, or may be used to build new positioning or timing systems, such as indoor positioning, asset tracking, phase calibration in smart meters for power distribution, etc.
Generally speaking, the space time calibration (STC) technology provides a framework for determining positioning and timing within a network of devices. The technology captures clock stamp values of independent clocks in network nodes upon transmission and/or receipt of signals transmitted between the nodes (called “pings”). It collects and organizes the clock stamp data for a grouping of nodes that communicate with each other over a time interval. In some embodiments, the nodes share clock stamps of pings in a data structure referred to as a “pung” or pung packet. For data collected over a solution interval, the technology formulates a system of equations to solve for location and/or timing parameters of the nodes in the network. The networks can be formed as an ad hoc network of mobile devices that communicate with each other using wireless communication techniques.
For more background on the STC technology, please see Assignee's U.S. Pat. Nos. 7,876,266, 7,983,185, Published US Patent Applications 20090233621 and 20090213828, and unpublished U.S. patent application Ser. No. 13/187,723 filed Jul. 21, 2011, entitled MULTI-PATH-COMPENSATION METHODS FOR LOCATION-DETERMINATION OF MOBILE DEVICES (Now published as US Patent Application Publication 2012-0309415), Ser. No. 13/179,807 filed Jul. 11, 2011, entitled LOCATION AWARE INTELLIGENT TRANSPORTATION SYSTEMS (Now U.S. Pat. No. 8,463,290), 61/613,915, filed Mar. 21, 2012, entitled Positioning Systems for Wireless Networks (included in this specification), 61/645,589, filed May 10, 2012, entitled Location Based Router (“LBR”)(included within this specification), which are hereby incorporated by reference in their entirety (referred to as “space-time calibration patents”).
U.S. Pat. No. 7,876,266 describes schemes for computing a differential solution for node position and clock parameters for a time interval, and for deriving an “asymptotic” solution from differential solutions over a series of time intervals. The STC technology computes a differential solution that provides estimates of the changes in positions of nodes and clock rates and offsets, for time elapsed since a last solution based on count stamp differentials between pairs of nodes, and a coarse direction vector. The count stamp differentials are measured directly from count stamps provided by the nodes. The coarse direction vector is an estimate of the direction between two nodes.
The STC computes “asymptotic” solutions from a series of differential solutions. These “asymptotic” solutions refine the differential solutions by leveraging the data computed over time to compute more accurate results. Ultimately, differential values for change in position and clock rate are used to compute position and timing of the nodes within a frame of reference. This frame of reference may be one that is provided externally, such as reference locations or clock values provided by another system or known by some direct measurement. The frame of reference may be formed dynamically over time, as a composite solution computed from estimates of the position and clock parameters of one or more nodes in a network of devices.
One challenge of a differential approach is that errors in each differential solution may be compounded when combined together. U.S. Pat. No. 7,876,266 points to ways to address this error. This disclosure builds on the previous disclosure by detailing state models and applications of them for determining position and timing of nodes in ad hoc networks.
One aspect of the invention is a method for determining location and timing for nodes in a network. In this network, at least one, and possibly more, of the nodes is moving, and the nodes have free running clocks, with corresponding clock errors. The clock errors, in one embodiment, comprise clock rate and offset errors relative to a reference clock.
The method computes location and timing of nodes using a model of network state that provides updates to the state based on an estimate from a previous time interval and observations captured over a time interval. The method obtains observations of clock stamps for transmissions between nodes occurring over a time interval. It applies the observations to a model of network state. From this model, the method generates an update of network state based on the observations and an estimate of the network state. The network state provides estimates of location parameters and clock parameters of the nodes in the network.
In one embodiment, the method computes error in node position and timing for the time interval based on the observations and adds that error to the previous estimate to compute the update of position and timing.
The model of network state uses a linearized expression of position error. In one embodiment, the model of network state models position error of network nodes using a coarse direction vectors (CDVs) representing coarse directions between corresponding pairs of nodes. The CDV provides a way to linearize relationships between the error in a position of a node and a difference between estimated distances and observed distances based on flight times between a pair of nodes. In alternative embodiments, other approaches can be used to linearize position/timing relationships between nodes. The position error may be modeled using a quadratic equation (e.g., the square root of the sum of squares). This formulation of error can then be linearized using derivatives (differentiation of non-linear expressions of relationships). One systematic approach to linearizing non-linear equations is to use an Extended Kalman filter.
In one embodiment, the network state model is based on statistical properties of clocks within the nodes. While alternative Bayesian models may be applied, one embodiment of the model applies a Kalman filter based model.
In one embodiment, the model comprises a model of location error of nodes. For each new time interval the model provides an update of position of a node by adding a current estimate of node position error to a previous solution for node position. The state of the position of a node is initialized in the model as near a reference position. This is the initial estimate from which position error is estimated by the model based on observations of clock stamp data captured over a first interval. Subsequent estimates are determined recursively using the update as the estimate for the node position and calculating a new position error based on observations in the next interval.
Another aspect of the invention is a system for determining location and timing for nodes in a network. The system comprises a router, processing agent and solution agent. The router communicates with the nodes to receive ping data transmitted between the nodes. The ping data comprises observations of clock count stamps from clocks in the nodes for pings transmitted between pairs of the nodes.
The processing agent communicates with the router for receiving the ping data and organizing the ping data for a time interval.
The solution agent receives the organized ping data from the processing agent and applies the organized ping data to a model of network state. The solution agent generates from the model an update of network state based on the observations and an estimate of the network state. The network state provides estimates of location parameters and clock parameters of the nodes in a network.
In one embodiment, the system includes a grouping agent that communicates with the router to establish the network of nodes that participate in providing the ping data used to update the network state for a solution interval. The grouping agent communicates with the processing agent to identify the nodes that form the network for determining position and timing solutions by the solution agent. The processing agent, in turn, uses this identification of the nodes participating in the network to extract, sort and formulate count stamps.
In one embodiment, the solution agent uses a model of position error state, and updates that mode recursively for new observations in corresponding time intervals. The solution agent computes an update to node position and node timing parameters for a current time interval based on an estimate for that interval, and count stamps obtained from network nodes during the current time interval. The solution agent uses the updated position computed for nodes from a prior time interval for the estimate of position for the current time interval.
Another aspect of the invention is a method for determining position of a network of devices. This method receives timing for transmission of signals between pairs of nodes in a network. The timing provides time of flight of the signals based on internal, free running clocks in the nodes. The method initializes a model of state of position of the nodes in the network, and updates the model of state based on observations of the timing over a time interval to provide an estimate of positions of the node based on an input estimate position and the observations. Further features will become apparent with reference to the following detailed description and accompanying drawings.